UVa/11484 - Document Object Model/document.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <stack>
   4 #include <string>
   5 #include <cassert>
   6 using namespace std;
   7
   8 #define D(x) cout << #x " es " << x << endl
   9
  10 int main(){
  11     int n, C=1;
  12     while (cin >> n && n){
  13         string line;
  14         getline(cin, line);
  15         int m = n/2;
  16         string content[m];
  17         int parent[m];
  18         parent[0] = -10000;
  19         vector<int> childs[m];
  20         stack<int> stk;
  21         for (int x = 0, i = 0; x < n; ++x){
  22             getline(cin, line);
  23             if (line == "</n>"){
  24               stk.pop();
  25             }else{
  26                string s = "";
  27                int j = line.find_first_of("'");
  28                char delimiter = line[j];
  29                while (assert(j < line.size()), line[++j] != delimiter){
  30                   s += line[j];
  31                }
  32                content[i] = s;
  33                if (stk.size() > 0){
  34                   childs[stk.top()].push_back(i);
  35                   parent[i] = stk.top();
  36                   //D(parent[i]), D(content[i]);
  37                }
  38                stk.push(i);
  39                ++i;
  40             }
  41         }
  42
  43         int p = 0, q = 0; //p = nodo en donde estoy, q = id de p en la lista de sus hermanos
  44         int I;
  45         cout << "Case " << C++ << ":" << endl;
  46         cin >> I;
  47         while (I--){
  48            string s;
  49            cin >> s;
  50            int x, y;
  51            //D(s), D(p), D(q);
  52            bool valid = true;
  53            if (s == "first_child"){
  54                if (childs[p].size() <= 0) valid = false;
  55                else{
  56                    x = childs[p][0];
  57                    y = 0;
  58                }
  59            }else if (s == "next_sibling"){
  60                  y = q+1;
  61                  if (parent[p] < 0 || y >= childs[parent[p]].size()) valid = false;
  62                  else x = childs[parent[p]][y];
  63            }else if (s == "previous_sibling"){
  64                  y = q-1;
  65                  if (parent[p] < 0 || y < 0 || y >= childs[parent[p]].size()) valid = false;
  66                  else x = childs[parent[p]][y];
  67            }else if (s == "parent"){
  68                  x = parent[p], y = 0;
  69                  if (x < 0) valid = false;
  70            }
  71            //D(valid);
  72            if (valid){
  73                cout << content[x] << endl;
  74                p = x, q = y;
  75            }
  76            else cout << content[p] << endl;
  77         }
  78     }
  79     return 0;
  80 }